package com.dataStructures.sparsearray;

/**
 * 稀疏数组
 */
public class SparseArray {

	public static void main(String[] args) {
		// 1. 创建一个原始的二维数组
		int[][] chessArray1 = new int[11][11];
		chessArray1[1][2] = 1;
		chessArray1[2][3] = 2;
		chessArray1[4][5] = 2;

		// 输出原有二维数组
		System.out.println("原来的二维数组：");
		for (int[] rows : chessArray1) {
			for (int data : rows) {
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}

		// 2. 将二维数组转为稀疏数组
		// 得到非零数据的个数
		int sum = 0;
		for (int[] rows : chessArray1) {
			for (int data : rows) {
				if (data != 0) {
					sum++;
				}
			}
		}
		int[][] sparseArray = new int[sum + 1][3];
		sparseArray[0][0] = chessArray1.length;
		sparseArray[0][1] = chessArray1[0].length;
		sparseArray[0][2] = sum;

		// 遍历原二维数组，将不为0 的数据放入稀疏数组
		int count = 0;
		for (int i = 0; i < chessArray1.length; i++) {
			for (int j = 0; j < chessArray1[0].length; j++) {
				if (chessArray1[i][j] != 0) {
					count++;
					sparseArray[count][0] = i;
					sparseArray[count][1] = j;
					sparseArray[count][2] = chessArray1[i][j];
				}
			}
		}

		// 输出稀疏数组
		System.out.println("稀疏数组为：");
		for (int i = 0; i < sparseArray.length; i++) {
			System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]);
		}

		// 3. 稀疏数组恢复为二维数组
		int[][] chessArray2 = new int[sparseArray[0][0]][sparseArray[0][1]];
		for (int i = 1; i < sparseArray.length; i++) {
			chessArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
		}

		// 输出回复后的数组
		System.out.println("原来的二维数组：");
		for (int[] rows : chessArray2) {
			for (int data : rows) {
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}
	}
}
